<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>区间重叠问题</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="区间重叠问题">区间重叠问题</h1>
<ul>
<li><a href="https://labuladong.gitbook.io/algo/dong-tai-gui-hua-xi-lie/tan-xin-suan-fa-zhi-qu-jian-tiao-du-wen-ti">https://labuladong.gitbook.io/algo/dong-tai-gui-hua-xi-lie/tan-xin-suan-fa-zhi-qu-jian-tiao-du-wen-ti</a></li>
</ul>
<h1 id="1-基础问题">1. 基础问题</h1>
<p>言归正传，本文解决一个很经典的贪心算法问题 Interval Scheduling（区间调度问题）。给你很多形如 [start, end] 的闭区间，请你设计一个算法，算出这些区间中最多有几个互不相交的区间。</p>
<pre><code>int intervalSchedule(int[][] intvs) {}
</code></pre>
<p>举个例子，intvs = [[1,3], [2,4], [3,6]]，这些区间最多有 2 个区间互不相交，即 [[1,3], [3,6]]，你的算法应该返回 2。注意边界相同并不算相交。
这个问题在生活中的应用广泛，比如你今天有好几个活动，每个活动都可以用区间 [start, end] 表示开始和结束的时间，请问你今天最多能参加几个活动呢？显然你一个人不能同时参加两个活动，所以说这个问题就是求这些时间区间的最大不相交子集。</p>
<p>正确的思路其实很简单，可以分为以下三步：</p>
<ul>
<li>从区间集合 intvs 中选择一个区间 x，这个 x 是在当前所有区间中结束最早的（end 最小）。</li>
<li>把所有与 x 区间相交的区间从区间集合 intvs 中删除。</li>
<li>重复步骤 1 和 2，直到 intvs 为空为止。之前选出的那些 x 就是最大不相交子集。</li>
</ul>
<pre><code class="language-java"><div><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">intervalSchedule</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[][] intvs)</span> </span>{
    <span class="hljs-keyword">if</span> (intvs.length == <span class="hljs-number">0</span>) <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
    <span class="hljs-comment">// 按 end 升序排序</span>
    Arrays.sort(intvs, <span class="hljs-keyword">new</span> Comparator&lt;<span class="hljs-keyword">int</span>[]&gt;() {
        <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">compare</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] a, <span class="hljs-keyword">int</span>[] b)</span> </span>{
            <span class="hljs-keyword">return</span> a[<span class="hljs-number">1</span>] - b[<span class="hljs-number">1</span>];
        }
    });
    <span class="hljs-comment">// 至少有一个区间不相交</span>
    <span class="hljs-keyword">int</span> count = <span class="hljs-number">1</span>;
    <span class="hljs-comment">// 排序后，第一个区间就是 x</span>
    <span class="hljs-keyword">int</span> x_end = intvs[<span class="hljs-number">0</span>][<span class="hljs-number">1</span>];
    <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span>[] interval : intvs) {
        <span class="hljs-keyword">int</span> start = interval[<span class="hljs-number">0</span>];
        <span class="hljs-keyword">if</span> (start &gt;= x_end) {
            <span class="hljs-comment">// 找到下一个选择的区间了</span>
            count++;
            x_end = interval[<span class="hljs-number">1</span>];
        }
    }
    <span class="hljs-keyword">return</span> count;
}
</div></code></pre>
<p>本题要按照end排序， 不能按照start排序， 反例的话，可以参考下面#6 的反例 [(80,85),(77,86),(64,74),(77,78),(71,74)]</p>
<h1 id="2-leetcode-第-435-题无重叠区间">2. leetcode 第 435 题，无重叠区间</h1>
<ul>
<li><a href="https://leetcode.com/problems/non-overlapping-intervals/">https://leetcode.com/problems/non-overlapping-intervals/</a></li>
</ul>
<p>我们已经会求最多有几个区间不会重叠了，那么剩下的不就是至少需要去除的区间吗</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">eraseOverlapIntervals</span><span class="hljs-params">(self, intervals: List[List[int]])</span> -&gt; int:</span>
        intervals.sort(key = <span class="hljs-keyword">lambda</span> x:x[<span class="hljs-number">1</span>])
        n = len(intervals)
        num = <span class="hljs-number">0</span>
        end_current = -float(<span class="hljs-string">'inf'</span>)
        <span class="hljs-keyword">for</span> start, end <span class="hljs-keyword">in</span> intervals:
            <span class="hljs-keyword">if</span> start &gt;= end_current:
                num += <span class="hljs-number">1</span>
                end_current = end
        <span class="hljs-keyword">return</span> n - num
    
</div></code></pre>
<h1 id="3-第-452-题用最少的箭头射爆气球">3. 第 452 题，用最少的箭头射爆气球</h1>
<ul>
<li><a href="https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/">https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/</a></li>
</ul>
<p>其实稍微思考一下，这个问题和区间调度算法一模一样！如果最多有 n 个不重叠的区间，那么就至少需要 n 个箭头穿透所有区间：</p>
<p>只是有一点不一样，在 intervalSchedule 算法中，如果两个区间的边界触碰，不算重叠；而按照这道题目的描述，箭头如果碰到气球的边界气球也会爆炸，所以说相当于区间的边界触碰也算重叠：</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">findMinArrowShots</span><span class="hljs-params">(self, points: List[List[int]])</span> -&gt; int:</span>
        points.sort(key = <span class="hljs-keyword">lambda</span> x:x[<span class="hljs-number">1</span>])
        num = <span class="hljs-number">0</span>
        end_c = -float(<span class="hljs-string">'inf'</span>)
        <span class="hljs-keyword">for</span> start, end <span class="hljs-keyword">in</span> points:
            <span class="hljs-keyword">if</span> start &gt; end_c:
                num += <span class="hljs-number">1</span>
                end_c = end
        <span class="hljs-keyword">return</span> num
</div></code></pre>
<h1 id="4-只有一个会议室最多能安排多少个会议">4. 只有一个会议室，最多能安排多少个会议</h1>
<p>等同于# 2. 435问题</p>
<h1 id="5-252-一个人能否参加所有的会议而不冲突">5. 252 一个人，能否参加所有的会议而不冲突</h1>
<ul>
<li><a href="https://leetcode.com/problems/meeting-rooms">https://leetcode.com/problems/meeting-rooms</a></li>
</ul>
<p>一个人，是否能参加所有的会议室而不冲突。 和435解法其中一样。 435里面，如果有n个会议室， 最后能安排的不冲突的会议室也是n个， 那么252的答案就是true, 否则是false</p>
<h1 id="6-253-已知会议安排最少需要多少个会议室才不冲突-按照start排序">6. 253. 已知会议安排，最少需要多少个会议室才不冲突？ 按照start排序</h1>
<ul>
<li><a href="https://leetcode.com/problems/meeting-rooms-ii">https://leetcode.com/problems/meeting-rooms-ii</a></li>
<li>同一个时间点最多有多少个会议同时举行</li>
<li>等价问题 lintcode 391 飞机调度，同一个时间点最多有多少个飞机在天上飞</li>
</ul>
<p>解法如下:</p>
<ul>
<li>设置小顶堆，<strong>按照(结束时间)排序</strong></li>
<li>对会议(飞机)按照<strong>按照(开始时间,结束时间), 或者只按照(开始时间)排序</strong></li>
<li>逐个遍历e1, 和堆顶元素e2比较，如果e1开始时间大于等于e2的结束时间， 就pop(), 再push(e1)</li>
<li>最后看小顶堆里面还有多少个元素，就是答案</li>
</ul>
<pre><code class="language-python"><div><span class="hljs-string">"""
Definition of Interval.
class Interval(object):
    def __init__(self, start, end):
        self.start = start
        self.end = end
"""</span>
<span class="hljs-keyword">import</span> heapq

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-string">"""
    @param airplanes: An interval array
    @return: Count of airplanes are in the sky.
    """</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">countOfAirplanes</span><span class="hljs-params">(self, airplanes)</span>:</span>
        <span class="hljs-comment"># write your code here</span>
        airplanes2 = sorted([(x.start, x.end) <span class="hljs-keyword">for</span> x <span class="hljs-keyword">in</span> airplanes])
        s = []
        <span class="hljs-keyword">for</span> start, end <span class="hljs-keyword">in</span> airplanes2:
            <span class="hljs-keyword">if</span> s <span class="hljs-keyword">and</span> s[<span class="hljs-number">0</span>][<span class="hljs-number">0</span>] &lt;= start:
                heapq.heappushpop(s, (end, start))
            <span class="hljs-keyword">else</span>:
                heapq.heappush(s, (end, start))
        <span class="hljs-keyword">return</span> len(s)
</div></code></pre>
<p>本题还有一个不容易想到的解法</p>
<pre><code class="language-python"><div>ends = [x.end <span class="hljs-keyword">for</span> x <span class="hljs-keyword">in</span> airplanes]
starts = [x.start <span class="hljs-keyword">for</span> x <span class="hljs-keyword">in</span> airplanes]
ends.sort()
starts.sort()
end_pos = <span class="hljs-number">0</span>
<span class="hljs-keyword">for</span> start <span class="hljs-keyword">in</span> starts:
    <span class="hljs-keyword">if</span> start &gt;= ends[end_pos]:
        end_pos += <span class="hljs-number">1</span>
<span class="hljs-keyword">return</span> len(ends) - end_pos
</div></code></pre>
<h2 id="本题不能按照end-来排序-必须按照start-end排序-或者按照start排序">本题不能按照end 来排序, 必须按照(start, end)排序, 或者按照start排序</h2>
<p>下面是一个反例， 假设5个会议</p>
<pre><code>[(20,22),(17,26),(4,14),(17,18),(11,14)]


1. (4,14)
2. (11,14)
3. (17,18)
4. (17,26)
5. (20,22)
</code></pre>
<p>如果按照 start 排序遍历， 那么只需要2个会议室</p>
<pre><code> 1          3          5  
-----     ------     -------            会议室1
   2        4
  ---     --------------------------    会议室2
</code></pre>
<p>如果按照 end 排序遍历，那么就需要3个会议室. 关键是先安排会议5，就会抢占了会议室2， 导致再安排会议4的时候，会议室1和2都没空，只能用会议室3了</p>
<pre><code> 1          3          
-----     ------                        会议室1
   2                   5
  ---                -------            会议室2
            4
          --------------------------    会议室3
</code></pre>
<h1 id="6b-leetcode-1094-car-pooling">6b. leetcode 1094. Car Pooling</h1>
<ul>
<li><a href="https://leetcode.com/problems/car-pooling/">https://leetcode.com/problems/car-pooling/</a></li>
<li>会议室问题的变形题目， 相当于只有一个会议室，多个会议可以公用，但是会议室有最大人数限制。</li>
<li>仍然按照start时间排序遍历，遍历到每个会议的时候，把之前已经结束的会议全部clean,再push当前的会议。</li>
<li>算法复杂度O(nlgn)</li>
</ul>
<pre><code class="language-python"><div><span class="hljs-keyword">import</span> heapq

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">carPooling</span><span class="hljs-params">(self, trips: List[List[int]], capacity: int)</span> -&gt; bool:</span>
        trips.sort(key = <span class="hljs-keyword">lambda</span> x:x[<span class="hljs-number">1</span>])
        s = []
        num_in_s = <span class="hljs-number">0</span>
        <span class="hljs-keyword">for</span> num,start,end <span class="hljs-keyword">in</span> trips:
            <span class="hljs-keyword">while</span> s <span class="hljs-keyword">and</span> s[<span class="hljs-number">0</span>][<span class="hljs-number">0</span>] &lt;= start:
                num_in_s -= s[<span class="hljs-number">0</span>][<span class="hljs-number">2</span>]
                heapq.heappop(s)
            heapq.heappush(s, (end,start,num))
            num_in_s += num
            <span class="hljs-keyword">if</span> num_in_s &gt; capacity:
                <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
        <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>
    
</div></code></pre>
<p>本题还有一个解法, 时间复杂度O(n), 但是空间利用率不高</p>
<pre><code><code><div>class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -&gt; bool:
        matrix = [0] * 1001
        for passenger,start,end in trips:
            matrix[start] += passenger
            matrix[end] -= passenger
            
        for i in range(1001):
            capacity -= matrix[i]
            if capacity &lt; 0:
                return False
            
        return True
</div></code></code></pre>
<p>在上面的思路提示下，可以改进一下空间利用率，但是因为引入了排序，时间复杂度还是O(nlgn)</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">carPooling</span><span class="hljs-params">(self, trips: List[List[int]], capacity: int)</span> -&gt; bool:</span>
        events = []
        <span class="hljs-keyword">for</span> trip <span class="hljs-keyword">in</span> trips:
            events.append((trip[<span class="hljs-number">1</span>], trip[<span class="hljs-number">0</span>]))
            events.append((trip[<span class="hljs-number">2</span>], -trip[<span class="hljs-number">0</span>]))
        events.sort()
        c = <span class="hljs-number">0</span>
        <span class="hljs-keyword">for</span> event <span class="hljs-keyword">in</span> events:
            c += event[<span class="hljs-number">1</span>]
            <span class="hljs-keyword">if</span> c &gt; capacity:
                <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
        <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>
</div></code></pre>
<h1 id="7-leetcode-56-区间覆盖问题-按照start排序">7. leetcode 56 区间覆盖问题, 按照start排序</h1>
<ul>
<li><a href="https://leetcode.com/problems/merge-intervals/">https://leetcode.com/problems/merge-intervals/</a></li>
<li>按照start排序，就可以从前往后遍历</li>
<li>按照end排序， 就需要从后往前遍历</li>
</ul>
<p>简介</p>
<pre><code><code><div>Given a collection of intervals, merge all overlapping intervals.
Example 1:
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Example 2:
Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.
</div></code></code></pre>
<p>代码</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">merge</span><span class="hljs-params">(self, intervals: List[List[int]])</span> -&gt; List[List[int]]:</span>
        <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> intervals:
            <span class="hljs-keyword">return</span> []
        intervals.sort(key=<span class="hljs-keyword">lambda</span> x:x[<span class="hljs-number">0</span>])
        ans = []
        start, end = intervals[<span class="hljs-number">0</span>]
        <span class="hljs-keyword">for</span> interval <span class="hljs-keyword">in</span> intervals[<span class="hljs-number">1</span>:]:
            <span class="hljs-keyword">if</span> interval[<span class="hljs-number">0</span>] &lt;= end:
                end = max(end, interval[<span class="hljs-number">1</span>])
                start = min(start, interval[<span class="hljs-number">0</span>])
            <span class="hljs-keyword">else</span>:
                ans.append([start, end])
                start, end = interval[<span class="hljs-number">0</span>], interval[<span class="hljs-number">1</span>]
            <span class="hljs-comment">#print(f"{interval} {start} {end}")</span>
        ans.append([start, end])
        <span class="hljs-keyword">return</span> ans
</div></code></pre>
<p>如果按照end排序，为什么不能从前往后遍历. 反例可以参考 前面 “#6. 253. 已知会议安排”。</p>
<h2 id="变种题目7b-leetcode-495-teemo-attacking">变种题目7b leetcode 495. Teemo Attacking</h2>
<ul>
<li><a href="https://leetcode.com/problems/teemo-attacking/">https://leetcode.com/problems/teemo-attacking/</a></li>
<li>给定的列表 [ts1, ts2, ts3] , duration.  相当于区间 [[ts1,ts1+duration], [ts2,ts2+duration], [ts3,ts3+duration] ]</li>
<li>相当于求这个区间列表覆盖的总长度。</li>
</ul>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">findPoisonedDuration</span><span class="hljs-params">(self, timeSeries: List[int], duration: int)</span> -&gt; int:</span>
        ans = <span class="hljs-number">0</span>
        start = <span class="hljs-number">0</span>
        end = <span class="hljs-number">0</span>
        <span class="hljs-keyword">for</span> ts <span class="hljs-keyword">in</span> timeSeries:
            <span class="hljs-keyword">if</span> ts &gt; end:
                ans += end - start
                start = ts
                end = ts + duration
            <span class="hljs-keyword">else</span>:
                end = ts + duration
        ans += end - start
        
        <span class="hljs-keyword">return</span> ans
</div></code></pre>
<h2 id="7c-lc-1288-remove-covered-intervals">7c. LC 1288 Remove Covered Intervals</h2>
<ul>
<li><a href="https://leetcode.com/problems/remove-covered-intervals/">https://leetcode.com/problems/remove-covered-intervals/</a></li>
</ul>
<p>Given a list of intervals, remove all intervals that are covered by another interval in the list. Interval [a,b) is covered by interval [c,d) if and only if c &lt;= a and b &lt;= d.</p>
<p>After doing so, return the number of remaining intervals.</p>
<pre><code><code><div>Example 1:

Input: intervals = [[1,4],[3,6],[2,8]]
Output: 2
Explanation: Interval [3,6] is covered by [2,8], therefore it is removed.
</div></code></code></pre>
<p>labuladong有篇文章讲了这道题, 下面是我的解法</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">removeCoveredIntervals</span><span class="hljs-params">(self, intervals: List[List[int]])</span> -&gt; int:</span>
        <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> intervals:
            <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>
        intervals.sort(key = <span class="hljs-keyword">lambda</span> x:(x[<span class="hljs-number">0</span>], -x[<span class="hljs-number">1</span>]))   <span class="hljs-comment"># 必须按照start升序，end降序来排列</span>
        cur_s, cur_e = intervals[<span class="hljs-number">0</span>]
        count = <span class="hljs-number">0</span>
        <span class="hljs-keyword">for</span> start, end <span class="hljs-keyword">in</span> intervals[<span class="hljs-number">1</span>:]:
            <span class="hljs-keyword">if</span> cur_e &gt;= end:
                count += <span class="hljs-number">1</span>
            <span class="hljs-keyword">elif</span> end &gt;= cur_e:
                cur_s, cur_e = start, end
                
        <span class="hljs-keyword">return</span> len(intervals) - count
    
</div></code></pre>
<p>如果只start升序， end也升序来排列，不好处理下面这种情况 (1,3), (1, 5)</p>
<pre><code><code><div>(1) start升序， end也升序, 覆盖的情况会被漏掉
    --------
    ------------

(2) start升序， end降序序
    ------------
    --------
</div></code></code></pre>
<h1 id="x-leetcode-相似但是属于其他类型的题目">X. leetcode 相似但是属于其他类型的题目</h1>
<h2 id="x1-986-interval-list-intersections">X.1 986. Interval List Intersections</h2>
<ul>
<li><a href="https://leetcode.com/problems/interval-list-intersections/">https://leetcode.com/problems/interval-list-intersections/</a></li>
<li>求两个已排序区间列表的相交部分</li>
<li>类似的题目，求两个已排序数组公告元素。双指针法</li>
</ul>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">intervalIntersection</span><span class="hljs-params">(self, A: List[List[int]], B: List[List[int]])</span> -&gt; List[List[int]]:</span>
        m = len(A)
        n = len(B)
        i = <span class="hljs-number">0</span>
        j = <span class="hljs-number">0</span>
        ans = []
        <span class="hljs-keyword">while</span> i &lt; m <span class="hljs-keyword">and</span> j &lt; n:
            <span class="hljs-keyword">if</span> A[i][<span class="hljs-number">0</span>] &gt; B[j][<span class="hljs-number">1</span>]:
                j += <span class="hljs-number">1</span>
            <span class="hljs-keyword">elif</span> B[j][<span class="hljs-number">0</span>] &gt; A[i][<span class="hljs-number">1</span>]:
                i += <span class="hljs-number">1</span>
            <span class="hljs-keyword">else</span>:
                ans.append([max(A[i][<span class="hljs-number">0</span>], B[j][<span class="hljs-number">0</span>]), min(A[i][<span class="hljs-number">1</span>], B[j][<span class="hljs-number">1</span>])])
                <span class="hljs-keyword">if</span> A[i][<span class="hljs-number">1</span>] == B[j][<span class="hljs-number">1</span>]:
                    i += <span class="hljs-number">1</span>
                    j += <span class="hljs-number">1</span>
                <span class="hljs-keyword">elif</span> A[i][<span class="hljs-number">1</span>] &gt; B[j][<span class="hljs-number">1</span>]:
                    j += <span class="hljs-number">1</span>
                <span class="hljs-keyword">else</span>:
                    i += <span class="hljs-number">1</span>
                    
        <span class="hljs-keyword">return</span> ans
</div></code></pre>
<h2 id="x2-leetcode-436-find-right-interval">X.2 leetcode 436. Find Right Interval</h2>
<ul>
<li><a href="https://leetcode.com/problems/find-right-interval/">https://leetcode.com/problems/find-right-interval/</a></li>
</ul>
<p>本题其实是二分查找问题</p>
<pre><code class="language-python"><div><span class="hljs-keyword">import</span> bisect

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">findRightInterval</span><span class="hljs-params">(self, intervals: List[List[int]])</span> -&gt; List[int]:</span>
        n = len(intervals)
        starts = sorted([(x[<span class="hljs-number">0</span>], i) <span class="hljs-keyword">for</span> i,x <span class="hljs-keyword">in</span> enumerate(intervals)])
        ans = []
        <span class="hljs-keyword">for</span> start, end <span class="hljs-keyword">in</span> intervals:
            pos = bisect.bisect_left(starts, (end, ))
            <span class="hljs-keyword">if</span> pos &lt; n:
                ans.append(starts[pos][<span class="hljs-number">1</span>])
            <span class="hljs-keyword">else</span>:
                ans.append(<span class="hljs-number">-1</span>)
        <span class="hljs-keyword">return</span> ans
</div></code></pre>
<h2 id="x3-weighted-job-scheduling-dynamic-programming">X.3 Weighted Job Scheduling Dynamic Programming</h2>
<ul>
<li><a href="https://www.youtube.com/watch?v=cr6Ip0J9izc&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=16">https://www.youtube.com/watch?v=cr6Ip0J9izc&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=16</a></li>
<li><a href="https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/WeightedJobSchedulingMaximumProfit.java">https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/WeightedJobSchedulingMaximumProfit.java</a></li>
</ul>
<p>给定一系列的任务 (start1, end1, value1), (start2, end2, value2), (start3, end3, value3)... 只有1个CPU, 如何调度选择，是总value最大。
初看像是区间覆盖问题，实际却类似于 最长递增子序列问题</p>
<pre><code><code><div>tasks = [(1,3,5), (2,5,6), (4,6,5), (6,7,4), (5,8,11), (7, 9,2)]

def dp_solve(tasks):
    n = len(tasks)
    dp = [0] * n
    ans = 0
    for i in range(n):
        dp[i] = tasks[i][2]
        for j in range(i):
            if tasks[j][1] &lt;= tasks[i][0]:
                dp[i] = max(dp[i], dp[j] + tasks[i][2])
        ans = max(ans, dp[i])
    return ans

def main():
    print(tasks)
    print(dp_solve(tasks))

if __name__ == '__main__':
    main()


</div></code></code></pre>
<h2 id="x4-134-gas-station">x.4 134. Gas Station</h2>
<ul>
<li><a href="https://leetcode.com/problems/gas-station/">https://leetcode.com/problems/gas-station/</a></li>
</ul>
<p>这道题最开始没有思路，看了讨论以后，排名最高的讨论基于2个推断给出了非常简单的解法</p>
<p><a href="https://leetcode.com/problems/gas-station/discuss/42568/Share-some-of-my-ideas">https://leetcode.com/problems/gas-station/discuss/42568/Share-some-of-my-ideas</a>.</p>
<ol>
<li>如果 从 station[i]出发不能到达 station[j], 那么从i ~ j范围的加油站都不能作为起点， 需要尝试从j+1出发</li>
<li>如果 总油量 &gt;= 总消耗的油量， 那么一定有解。</li>
</ol>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">canCompleteCircuit</span><span class="hljs-params">(self, gas, cost)</span> -&gt; int:</span>
        total = <span class="hljs-number">0</span>
        tank = <span class="hljs-number">0</span>
        start_p = <span class="hljs-number">0</span>
        m = len(gas)
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(m):
            tank += gas[i] - cost[i]
            <span class="hljs-keyword">if</span> tank &lt; <span class="hljs-number">0</span>:
                total += tank
                tank = <span class="hljs-number">0</span>
                start_p = i + <span class="hljs-number">1</span>
        <span class="hljs-keyword">if</span> total + tank &gt;= <span class="hljs-number">0</span>:
            <span class="hljs-keyword">return</span> start_p
        <span class="hljs-keyword">else</span>:
            <span class="hljs-keyword">return</span> <span class="hljs-number">-1</span>
</div></code></pre>
<p>上面代码关于total的累加不是太好理解，改成下面这样更好</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">canCompleteCircuit</span><span class="hljs-params">(self, gas, cost)</span> -&gt; int:</span>
        total = <span class="hljs-number">0</span>
        tank = <span class="hljs-number">0</span>
        start_p = <span class="hljs-number">0</span>
        m = len(gas)
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(m):
            total += gas[i] - cost[i]
            tank += gas[i] - cost[i]
            <span class="hljs-keyword">if</span> tank &lt; <span class="hljs-number">0</span>:
                tank = <span class="hljs-number">0</span>
                start_p = i + <span class="hljs-number">1</span>
        <span class="hljs-keyword">if</span> total&gt;= <span class="hljs-number">0</span>:
            <span class="hljs-keyword">return</span> start_p
        <span class="hljs-keyword">else</span>:
            <span class="hljs-keyword">return</span> <span class="hljs-number">-1</span>
</div></code></pre>

    </body>
    </html>